package org.example.algorithm.hash;

import java.util.HashMap;
import java.util.HashSet;

public class LongestConsecutiveSolution {

    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        HashSet<Integer> numSet = new HashSet<>();
        for (int num: nums) {
            numSet.add(num);
        }
        int maxLen = Integer.MIN_VALUE;
        for (int num: numSet) {
            //!!!关键判断
            if (numSet.contains(num+1)) {
                continue;
            }
            int tempLen = 1;
            int checkKey = num - 1;
            while(numSet.contains(checkKey)) {
                tempLen++;
                checkKey--;
            }
            if (tempLen > maxLen) {
                maxLen = tempLen;
            }
        }
        return maxLen;
    }

    public int longestConsecutive2(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        HashMap<Integer, Boolean> numMap = new HashMap<>();
        for (int num: nums) {
            numMap.put(num, true);
        }
        int maxLen = Integer.MIN_VALUE;
        int maxStart = Integer.MIN_VALUE;
        for (int i=0;i<nums.length;i++) {
            if (nums[i] <= maxStart && nums[i] >= maxStart - maxLen + 1) {
                continue;
            }
            int tempLen = 1;
            int checkKey = nums[i] - 1;
            while(numMap.containsKey(checkKey)) {
                tempLen++;
                checkKey--;
            }
            if (tempLen > maxLen) {
                maxLen = tempLen;
                maxStart = nums[i];
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {100,4,200,1,3,2,8,5,6};
        LongestConsecutiveSolution solution = new LongestConsecutiveSolution();
        int res = solution.longestConsecutive(nums);
        System.out.println(res);
    }
}
